/*
四数之和
   class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        int n = nums.length;
        if (n < 4) {
            return ret;
        }
        // 1.排序数组
        Arrays.sort(nums);
        // 2.固定第一个数 i
        for (int i = 0; i < n; i++) {
            // 去重 i
            if(i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            // 3.在接下来的数字中找和为 target - nums[i]
            // 4.继续固定一个数 j
            int j = i + 1;
            for(;j < n ; j++) {
                //去重 j
                if(j > i + 1 && nums[j] == nums[j-1]) {
                    continue;
                }
                // 5. 在接下来的数组中找到 target - nums[i] - nums[j]
                long t = (long)target - nums[i] - nums[j];
                // 6 定义双指针 找到和为t
                int left = j + 1 , right = n - 1;
                while(left < right) {
                    long sum = nums[right] + nums[left];
                    if(sum == t) {
                        ret.add(Arrays.asList(nums[left],nums[right],nums[i],nums[j]));
                        left++; right--;
                        //7.去重left 和 right
                        while(left < right && nums[left] == nums[left-1]) {
                            left++;
                        }
                        while(left < right && nums[right] == nums[right+1]) {
                            right--;
                        }
                    }else if(sum < t){
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return ret;
    }
}

前 K 个高频元素
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];
        HashMap<Integer,Integer> hash = new HashMap<>();
        //全部丢进哈希表中
        for(int x : nums) {
            hash.put(x,hash.getOrDefault(x,0)+1);
        }
        //创建小根堆 按照数字频率从小到大
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a,b)->hash.get(a) - hash.get(b));
        //遍历hash 维护一个大小为k的小跟堆
        for(Map.Entry<Integer,Integer> entry : hash.entrySet()) {
            //拿出次数 为后续作比较
            int value = entry.getValue();
            // 如果小跟堆大小不足k 先加入
            if(minHeap.size() < k) {
                minHeap.offer(entry.getKey());
            }else {
                //拿出堆顶 为最小次数
                // 此时 小跟堆存储的为key
                int top = hash.get(minHeap.peek());
                // 如果发现此时堆顶 没有 value 大 那么它将被弹出
                if(top < value) {
                    minHeap.poll();
                    minHeap.offer(entry.getKey());
                }
            }
        }
        //遍历minheap  加入到最终结果
        int index = 0;
        for(int n : minHeap) {
            ret[index++] = n;
        }
        return ret;



    }
}
 */